\documentclass[a4paper,12pt] {report}
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{mathrsfs}
\setcounter{secnumdepth}{4}
\setcounter{tocdepth}{4} 
\usepackage{comment}


\title{Projet de compilation Léa 2012 \\ Université de Bordeaux I \\Sciences et Technologies}
\author{\textsc{Parant Sarah} - \textsc{Castagnet Florian} -\\ \textsc{Etcheverry Jeremy} - \textsc{Paziewski Hayley}}
\date{\today} 
\begin{document}
\maketitle 
\tableofcontents
\chapter*{Introduction}
Au cours du semestre 7 d'informatique à l'Université de Bordeaux 1, nous avons dû réaliser un compilateur d'un langage s'appelant Lea. Ce langage permettra un enseignement efficace de la programmation à des étudiants novices en la matière. Ce projet était à réaliser par groupe de 4 personnes reparties comme tel :\\ 
\begin{itemize}
\item Un(e) correspondant(e) qui est chargé(e) de représenter le groupe, ainsi que de faire ce rapport.
\item Un(e) syntacticien(ne) s'assurant de la partie grammaire et reconnaissance de caractères dans le fichier d'entrée.
\item Un(e) sémanticien(ne) qui va produire le code intermédiaire.
\item Un développeur qui écrira le code cible produit par notre compilateur.\\
\end {itemize}

Nous avons eu approximativement 2 mois pour réaliser ce projet assez conséquent.
L'objectif est donc, à partir d'un fichier source Lea, d'obtenir un fichier JAVA, grâce à notre compilateur.\\\\
Pour tester notre projet, nous fournissons sept fichiers tests plus ou moins complets. Ces fichiers se trouvent dans le dossier data. Ce dossier contiendra plusieurs fichiers :\\\\

\begin{itemize}
\item Le fichier arbreSynt.dot qui contiendra l'arbre syntaxique de notre programme. Il faut utiliser le logiciel dotty pour pouvoir visionner l'arbre sous forme graphique
\item Le fichier Env.dot représentait nos différents environnements. Mais nous n'avons pas continué à les utiliser car ils nous causaient beaucoup d'erreurs de parse.
\item Les sept fichiers input.txt contenant différent code lea, traduit par notre compilateur.
\item Un fichier output.txt qui présente le parcours de notre compilateur sur le langage Léa.\\\\
\end {itemize}

Le résultat de cette compilation se trouve dans le fichier MyFich.java. Il correspond donc à la transposition du langage Léa au langage JAVA.\\\\
Pour tester nos fichiers d'entrées, il faut changer la valeur arg de la règle défault. Nous n'avons pas réussi à créer autant de fichiers output que de fichiers input automatiquement.\\\\
Pour réussir ce projet, nous avons créé un dépôt svn google code pour un travail versionné et collaboratif.

\chapter{Cahier des charges}
\section{Contexte}
\subsection{Principe de ce langage}
Ce langage (aussi nommé Langage élémentaire algorithmique) est un moyen d'enseigner la programmation à des étudiants suivant un cursus totalement différent d'un cursus informatique. Il permettra d'apprendre les bases de la programmation dynamique. Ce langage s'inspire des langages de programmation Pascal, Ruby et Python.
\subsection{Pourquoi celui-ci}
Ce langage est très simple, d'une part, à enseigner les principes de la programmation, et d'autre part, d'assimiler la programmation ainsi que la programmation objet. Il est aussi beaucoup plus simple que le langage cible que l'on doit atteindre à la fin de ce projet (JAVA). Ce langage ne se soucie pas des bibliothèques à importer.
\section{Objectifs}
L'objectif de ce projet est donc d'implémenter un compilateur qui transformera un code en Lea en un code JAVA. Ce compilateur doit être écrit en CUP/JFLEX/JAVA.\\
JFLEX est un générateur d'analyse lexicale, il permet de reconnaître des symboles dans un code (des identifiants, des nombres, ...). Il regroupe les lettres pour former des mots (tokens). Il peut aussi identifier s'il y a des commentaires et les supprimer, signaler les mots mal orthographiés.\\
CUP est ce qu'on appelle un parseur, il permet, grâce à une grammaire algébrique, de savoir si le code qu'il vérifie est syntaxiquement correcte.
\chapter{Choix retenus}
Pour commencer ce projet, nous nous sommes attribué les rôles de chacun des membres du groupe.\\
Bien évidemment, ce rapport relate le travail des membres du groupe dans un ordre précis suivant le déroulement normal du sujet. Chaque membre ayant travaillé sa partie, l'ordre décrit ici représente la mise en commun des travaux réalisés.\\\\
Ensuite, nous avons commencé le projet en lui-même en partant pratiquement de zéro. Nous nous sommes inspirés du tp5 fait en cours pour avoir une base solide. 
Nous avons modifié par la suite le fichier tp.jflex pour qu'il reconnaisse bien tous les mots-clés de notre fichier source (chaînes de caractères, nombres, mots-clé du langage). Notre lexeur permet aussi de ne pas tenir compte des commentaires présents dans le code source.\\\\
Nous avons ensuite commencé à faire la grammaire du langage. Cela nous a pris pas mal de temps car elle est assez longue et nous avons eu beaucoup de conflits a gérer. Notre grammaire possède une trentaine de règles, ce qui permet de reconnaître le langage.\\\\
Pour régler certains conflits, nous avons établi des règles de priorité entre par exemple les accolades, les parenthèses, etc.
Notre grammaire reconnaissant Lea a quelques différences avec celle donnée dans le sujet. En effet, un point-virgule est nécessaire après l'accolade fermante d'une structure ou d'une classe. Nous avons aussi considéré que les instructions ''list of'' seraient implémentées comme des tableaux, le sujet n'étant pas clair sur ce sujet. Ce sont les seules spécificités de notre grammaire.\\\\
Après avoir fait plusieurs tests sur notre grammaire, nous nous sommes mis sur la construction de l'arbre syntaxique. Celui-ci est indépendant de la grammaire, qui mémorise la structure du programme et les actions qui le composent. Notre arbre représente bien les éléments importants de notre programme. Celui-ci est complet.\\\\
Nous avons tenté ensuite de faire les environnements comme vus en td. Nous y avons passé beaucoup de temps sans arriver à les faire. En effet, ces environnements nous causaient beaucoup d'erreurs de parse que nous ne comprenions pas au début. Plus précisément, elles étaient dû au fait qu'on été obligé a cause de notre grammaire de mettre du code dans la partie gauche de nos règles. Or à partir d'un certain nombre, ça donnait des conflits, d'où les erreurs parses par enchaînement logique. Nous avons donc décidé de ne pas utilisé le code fournit de la classe Env et de coder les envirronnement par nous même en utilisant des tables de hashage, des listes ... contenant la liste des déclarations globales, ou les locales de chaques fonctions. Cela simulerait donc les environnements. Vous pourrez tout de même observer que nous avons laissé en commentaire certaines partie de notre utilisation de Env. De même que nous avons finis par comprendre d'où venait le problème et que sans celui-ci l'arbre des environnements se construisait bien. Nous détaillerons plus ce point dans la partie des problèmes ci-après. Nous avons tout de même laissé un exemple d'arbre d'environnement bon, Env.dot, pour un certain exemple.\\\\
Après avoir fini d'implémenter ces structures, nous avons implémenté trois autres fichiers cruciaux dans notre projet: le fichier Fonctions.java, le fichier Declarations.java et le fichier Prototypes.java.\\
\begin{itemize}
\item Commençons par Fonctions.java. Comme son nom l'indique, nous allons gérer tout ce qui concerne les fonctions dans ce fichier. Une table de hashage est utilisé afin de sauvegardé les fonctions de notre programme (Key : le prototype de la fonction, afin de pouvoir gérer les surcharges et Value : la Fonction). Celles-ci prennent en entrées la forme de la fonction (fonction, procedure, operateur, constructeur), le type, l'identifiant, les paramètres, tout le corps de la fonction, la liste des déclarations de la fonction (on a le nom de la décla, anisi que son type) et la liste des variable utilisé dans les instructions ligne par ligne (on a de même le nom et le type).\\
Ensuite, dans cette classe, nous utilisons toute sorte de fonctions. Voici, ci-dessous, l'utilité de certaines d'entres-elles.\\
Nous contrôlons bien la présence d'une fonction main, si ce n'est pas le cas, un pop-up est activé lors de la compilation pour le signifier à l'utilisateur. Nous contrôlons aussi que tous les types différents des types primitifs(int, boolean, etc..) soient bien déclarés comme structure ou classe (dans nos fichiers de tests, ça correspond par exemple a la variable T qui est un list of fiche, fiche étant le nom de la structure déclarée plus tôt). Si un type n'est pas déclaré, un nouveau pop-up est déclenché lors de la compilation pour le signaler à l'utilisateur.
On s'assure bien aussi que toutes les variables sont déclarées avant d'être utilisées. Pour cela, nous regardons qu'elles aient été déclaré soit dans les variables globales, soit dans les structures, les classes, dans la fonction ou ses paramètres et enfin dans un bloc de la fonction (par exemple un if). On vérifie par la même occasion qu'une variable n'est pas déclarée 2 fois dans le même bloc. Après avoir vérifié que tout cela fonctionnait, nous avons fait la vérification de type pour chaque instruction. Par exemple, une variable de type int ne pourra contenir que des éléments de type int. Cette partie n'est pas complète, car ça ne prend pas en compte les appels de fonction. De ce fait, si l'on a une instruction qui utilise que des int, mais avec un appel de fonction dont le paramètre est autre qu'un int, cela enverra une erreur, malgrès que l'appel de fonction retourne bien un int. Ce n'est juste que par manque de temps que cette spécificité n'a pas été gérée.\\
 \item le fichier Declarations.java va permettre de gérer les déclarations suivant une portèe. Une table de hashage permet de sauvegarder ces éléments. Ce fichier est aussi responsable de l'écriture dans le fichier de sortie des déclarations.\\
\item Pour finir, comme son nom l'indique, le fichier Prototypes.java va contenir les prototypes des fonctions permettant la création d'une interface dans notre fichier de sortie. Il gère donc aussi l'affichage des prototypes et contrôle que tous les prototypes sont implémentés par une fonction, si ce n'est pas le cas, un nouveau pop-up est déclenché.\\\\
Les fonctions read() et writeln(string) ont bien été implémenté comme dit dans le sujet. La fonction read va lire sur l'entrée standard alors que la fonction writeln(string) va écrire sur la sortie standard. L'argument string du writeln peut contenir des "+" pour bien simuler le véritable writeln.\\\\
Par choix d'implémentation, nous avons géré le type "list of" comme des tableaux. En effet, le sujet étant confus, nous avons décidé de l'implémenter ainsi.\\\\
De plus, la déclaration des variables locales et leurs initialisations doivent se faire en deux étapes. Par exemple, voici la déclaration et l'initialisation d'une déclaration : 
\begin{verbatim}
p1:Point; 
p2:Point;
p3:Point;  
p4:Point; 
p1 := null; 
p2 := null;  
p3 := null; 
p4 := null; 
\end{verbatim}

Toutes les déclarations doivent être faite avant l'initialisation de celles-ci .C'est également un choix d'implémentation car non précisé dans le sujet. Toutefois, on le gère bien dans les variables globales, comme demandé, la possibilité d'effectuer une initialisation et affectation en même temps : ex ( p1 : Point := null)\\\\
Nous avons aussi commencer à  gérer certains appels de fonctions présent dans l'API telle que la fonction random, length. Nous sauvegardons ces fonctions dans une table de hashage dédiée à cela.\\\\
Pour finir, nous avons modifié le fichier build.xml. Celui-ci permet d'exécuter plusieurs instructions. Il suit un ordre particulier qui est :\\
\begin{itemize}
\item Il lance la règle clean qui va supprimer tout le répertoire bin qui contient les fichiers .class, détruire l'archive demandée dans le sujet, détruire le dossier contenant la javadoc, détruire le fichier de sortie output.txt ainsi que la sortie JAVA MyFich.java, et pour finir détruira le fichier contenant l'abre syntaxique.
\item Puis il lance la règle défault qui va permettre de lancer notre compilateur en lançant l'analyseur lexical et l'analyseur syntaxique.
\item Ensuite, il va lancer la règle javadoc qui va permettre de la créer comme son nom l'indique. Nous avons fourni une documentation pour certains fichiers tels que Fonctions.java mais elle est courte par manque de temps. Cette documentation se situe dans le fichier doc fourni. La génération de cette javadoc provoque des erreurs lors de la compilation sur certaines machines. Mais cela ne pose aucun problème à sa construction ou à la compilation du projet. 
\item Pour finir, une archive nommée ``projet\_compil\_2012.tar'' sera créée grâce à la commande tar qui contiendra tous les fichiers importants de notre compilateur.
\item Il y a également juste un point qui n'est pas reconnu dans la grammaire car ce n'est pas précisé dans le sujet mais juste dans les exemple de code c'est la gestion de l'apostrophe.
C'est à dire, qu'on est censé pouvoir faire ( list of 'x ), or notre grammaire ne le reconnait pas. On s'en est rendus compte qu'a la fin mais c'est facilement corrigeable, c'est le même principe que les String qui sont gérés ( nom := "funcky" ) avec les doubles apostrophes.
\end{itemize}

\end{itemize}
\chapter{Problèmes envisagés/rencontrés}
\subsection{Problèmes envisagés}
 Plusieurs problèmes peuvent survenir que nous n'avons pas géré. Par exemple:
\begin{itemize}
 \item Nous ne vérifions pas si le type de retour d'une fonction est compatible avec le type de retour défini dans la signature, ce qui peut poser problème lors de la compilation du fichier de sortie JAVA (C'est par manque de temps car ce n'est pas compliqué).
\item Comme on n'a pu le voir avant, la vérification de type n'est pas complète. De ce fait, des pop-ups peuvent apparaitre pour des erreurs inexistantes comme dans le cas cité précedemment.
\item On c'est également rendus compte que des pop-up pouvaient apparaitre pour la vérification des types ou des déclarations lorsque l'on utilise des appels de champs à plusieurs ".".
  C'est-à-dire, par exemple (root.left.right.nom := "blabla") ne trouve pas que nom est de type String car on ne gère pas le multi-points. Notre vérif s'arrête au premier ".". C'est également car on a pas eu assez de temps.
\end{itemize}
\subsection{Problèmes rencontrés}
Comme dit plutôt, les environnements nous ont pris beaucoup de temps, nous avons essayé différentes solutions pour les implémenter mais à chaque fois, différentes erreurs de parse s'affichaient pour les raisons évoquées plus haut. En effet, notre grammaire nous obligé à mettre du code "\{: ... :\}" dans la partie gauche de nos règle, car on arrivait pas à détecté la fin du premier environnement des déclaration globales. Nous avons tout de même réfléchis à des solutions. L'une qui nous ai venu en premier en tête, est de modifier la gramaire en mettant une accolade ouvrante et une accolade fermante englobant les déclarations globales, nous permettant ansi de repérer facilement l'environement, un peu de la même façon que le tp5. Mais nous n'avons pas retenu cette solution.\\
Une autre solution aurait été au début de la grammaire avoir quelque chose du style : ( bloc::= ldecla lfonc) nous permettant ainsi de distinguer facilement la fin de la liste des déclarations globales. Ca nous mettait tout de même du code dans la partie gauche mais qu'une seule fois donc ça ne devrait pas posait de problème. Nous n'avons pas pu tester cette solution par manque de temps.\\\\
Une autre difficulté rencontrée a été la grammaire. Nous l'avons construite de zéro et il a fallu gérer les nombreux conflits qui sont survenus et s'adapter pour qu'elle fonctionne dans toutes les situations.\\\\
L'instruction CASE n'a pas été traité par manque de temps.\\
La vérification de types pour les appels de fonctions n'ont pas été implémenté. En effet, par exemple, l'instruction \begin{verbatim} s := s + parcours(root.left); \end{verbatim} ne fonctionne pas, un pop-up se déclenche car nous ne vérifions pas le type que renvoie la fonction parcours.\\\\
La synchronisation entre l'IDE eclipse et svn nous a souvent posé problème. Nous avons dû recommencer un dépot svn en plein milieu du projet car l'ancien ne fonctionnait plus. C'est notamment pour celà qu'il y a peu de révisions, en réalité, il y en a environ 130.

\chapter*{Conclusion}
En conclusion, nous pouvons dire que l'objectif principal de ce projet, c'est-à-dire créer un compilateur pour le langage Lea en JAVA est pratiquement atteint. Certes, des améliorations sont encore possible, mais la plus grosse partie du travail a été réalisé. Le fichier JAVA fournit n'est pas encore compilable à cause de petites erreurs de syntaxe facilement modifiable manuellement permettant de faire fonctionner le fichier java. On juge que notre projet est fonctionnel à hauteur de 90\% par rapport au langage Lea. Nous aurions aimé le finir mais le temps nous a manqué.\\\\
Ce projet nous a permis de mettre en avant les connaissances acquises lors de ce semestre en compilation, et une fois de plus, le travail de groupe a été l'élément-clé de la réussite de celui-ci.\\ 
Vous pourrez trouvez en annexe, un exemple de nos résultats pour le code donné à la fin de l'énoncé du projet, avec des ajouts supplémentaires.

\chapter{Annexe}
Code Léa 

\begin{verbatim}
/************************************** 
* un exemple complet de code lea ébtendu
*************************************** */
// Definition des constantes
MAX = 500;
operator >(a: fiche, b: fiche);
operator <(a: fiche, b: fiche);
operator *(a : int, b : int);
operator +(a : int);
// Définition des types
fiche = class {
           id : int;
           nom : string;
           age : int;

           fiche() {
               this.nom :="";
               this.age := 0;
              }
		
           operator >(a: fiche, b: fiche) {
                  return (a.age > b.age);
           }
		
           operator <(a: fiche, b: fiche) {
                  return (a.age > b.age);
           }
		
           operator *(a : int, b : int) {
                 return (a * b);
           }
		
          operator +(a : int) {
                return (a + 3);
           }		
};

fichebis = class {
        id : int;
       nom : string;
       age : int;

         fichebis() {
             this.nom :="";
             this.age := 0;
          }
		
     /* operator >(a: fiche, b: fiche) {
               return (a.age > b.age);
      }*/

};

// Déffinition d'une fonction
procedure sort(u:int , T : list of int) {
          echange : bool;
          repeat {
                 echange := false;
                 for j in [0 .. MAX-2] {
                       if(T[j] > T[j+1]) {
                           // Variable locale
                            aux : int;
                            aux := T[j];
                            T[j] := T[j+1];
                            T[j+1] := aux;
                            echange := true;
                     }
              }
        }while(echange);
        read();
}

function main(argn:int, argv: list of int): int {
     // Definition des variables
     table: list of fiche;
		
     // Instruction
     for i in [0 .. MAX-1] {
           table[i].nom :="";
           table[i].age :=random(100);
     }
     print("toto");
     return 0;
}
\end{verbatim}

Et voici le code JAVA créé :

\begin{verbatim}

import java.*;
import java.util.*;


public class MyFich implements MyInterface {

    public static final int MAX = 500;

    public class fichebis {
            int id;
            String nom;
            int age;

    public fichebis () {
           this.nom = "";
           this.age = 0;
   }

}

   public class fiche {
           int id;
           String nom;
           int age;
                  
        public fiche () {
            this.nom = "";
            this.age = 0;
        }

       public boolean operator0 (fiche a, fiche b) {
            return (a.age > b.age);
       }

      public boolean operator1 (fiche a, fiche b) {
            return (a.age > b.age);
       }

      public double operator2 (int a, int b) {
            return (a * b);
      }

     public double operator3 (int a) {
            return (a + 3);
     }

 }

 public static int main(int argn, int[] argv) {      

          fiche [] table = new fiche[10000];
                 for (int i = 0; i <MAX - 1; i++) {
                       table[i].nom = "";
                       table[i].age = random(100);
                 }
          System.out.println("toto");
          return 0;
 }

  public void sort(int u, int[] T) {
         boolean echange;
         do {
              echange = false;
              for (int j = 0; j <MAX - 2; j++) {
                    if(T[j] > T[j + 1]) {  
                       int aux;
                       aux = T[j];
                       T[j] = T[j + 1];
                       T[j + 1] = aux;
                       echange = true;
                   }
           }
     }
      while(echange);
      Scanner sr0= new Scanner(System.in);
  }   
}

\end{verbatim}

\end{document}
